package com.zjsru.plan2025.oneday;

import java.util.*;

/**
 * 2610. 转换二维数组
 *
 * @Author: cookLee
 * @Date: 2025-03-19
 */
public class FindMatrix {

    /**
     * 主
     * \
     * 二维数组应该 只 包含数组 nums 中的元素。
     * 二维数组中的每一行都包含 不同 的整数。
     * 二维数组的行数应尽可能 少 。
     * \
     * 输入：nums = [1,3,4,1,2,3,1]
     * 输出：[[1,3,4,2],[1,3],[1]]
     * 解释：根据题目要求可以创建包含以下几行元素的二维数组：
     * - 1,3,4,2
     * - 1,3
     * - 1
     * nums 中的所有元素都有用到，并且每一行都由不同的整数组成，所以这是一个符合题目要求的答案。
     * 可以证明无法创建少于三行且符合题目要求的二维数组。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        FindMatrix findMatrix = new FindMatrix();
        int[] nums = new int[]{1, 3, 4, 1, 2, 3, 1};
        System.out.println(findMatrix.findMatrix2(nums));
    }

    public List<List<Integer>> findMatrix(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<List<Integer>> ans = new ArrayList<>();
        while (!map.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            //使用迭代器,否则有修复异常
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Integer, Integer> entry = iterator.next();
                list.add(entry.getKey());
                if (entry.getValue() == 1) {
                    // 使用迭代器的 remove 方法安全地移除元素
                    iterator.remove();
                } else {
                    //更新剩余次数
                    map.put(entry.getKey(), entry.getValue() - 1);
                }
            }
            ans.add(list);
        }
        return ans;
    }

    public List<List<Integer>> findMatrix2(int[] nums) {
        var n = nums.length;
        var cnt = new int[n + 1];
        for (int num : nums) {
            cnt[num]++;
        }
        var ans = new ArrayList<List<Integer>>();
        for (var i = 1; i <= n; i++) {
            //获取该位数字的个数
            var cur = cnt[i];
            //遍历个数，如果存在可用数字进入循环
            for (var j = 0; j < cur; j++) {
                //如果答案数组的长度小于等于当前遍历的次数，则创建一个新数组，否则直接添加到答案数组中
                if (ans.size() <= j) {
                    ans.add(new ArrayList<>());
                }
                ans.get(j).add(i);
            }
        }
        return ans;
    }

}
